package com.xzz.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: hhz
 * @create: 2022-01-12 17:03
 * 452. 用最少数量的箭引爆气球
 *
 * 输入：points = [[10,16],[2,8],[1,6],[7,12]]
 * 输出：2
 * 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
 *
 **/
public class FindMinArrowShots {
    public static void main(String[] args) {
        System.out.println(findMinArrowShots(new int[][]{{10,16},{2,8},{1,6},{7,12}}));
    }
    public static int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));

        int count = 1;
        int end = points[0][1];
        for (int[] point : points) {
            int start = point[0];
            if(start>end){
                count++;
                end = point[1];
            }
        }
        return points.length-count;
    }
}
